(1) Field of the Invention
The present invention relates to a numerical array output device that converts an integer to an array, especially relates to the numerical array output device used for an encryption technique, an error correction technique and a digital signature technique as an information security technique.
(2) Description of the Prior Art
A private communication method is a method to have communication with a specific communication partner without leaking any communication content to anyone else. A digital signature method is a communication method that verifies communication content to the partner and proves a communication originator to be the person himself/herself. In this signature method, an encryption method called a public key encryption is used. The public key encryption is a method to easily manage an encryption key varied from each communication partner when there is more than one partner. This digital signature method is a mandatory and fundamental technology to communicate with multiple communication partners. To briefly explain the digital signature method, the encryption key in this method is different from the decryption key, and the decryption key is treated as private whereas the encryption key is in public. The public key encryption is described in detail in “Modern Encryption”, Industry Book 1997 written by Tatsuaki Okamoto and Hiroshi Yamamoto (hereinafter referred to as “Literature 1”).
One of the types of public key encryption is NTRU encryption. In this NTRU encryption, a code of the encryption is small in size compared with one of an elliptic curve encryption. The NTRU encryption code can be installed on a low-performance CPU such as one used for domestic appliances. Therefore, this encryption method has great future potential.
This NTRU encryption is described in detail in Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, “NTRU: A ring based public key cryptosystem”, Lecture Notes in Computer Science, 1423, pp. 267-288, Springer-Verlag, 1998 (referred to as “Literature 2”).
Here is the explanation for the NTRU encryption.
In general, all of polynomials for f(X) are expressed as:f(X)=f0+f1X+f2X2+ . . . +fN−1XN−1mod(XN−1)
Below polynomial f(X) is to be expressed in relation with an n-dimensional vector (f0, f1, f2 . . . , fN−1). Also, among this n-dimensional vector, the vector showing n 1 piece(s) of 1, n 2 piece(s) of −1, and other (n−n1−n2) piece(s) of 0 is expressed as L (n, n1, n2).
In this NTRU encryption, the decryption key is treated as a private key (hereinafter referred to as a private key), f (v) and Fp (v) are expressed with the following formula. A code attached with (v) such as f (v) and Fp (v) indicates a polynomial.Private key f(v)εa set of polynomials Lf, a set of polynomials Lf=L(263, 51, 50)Private key Fp(v)=private key f(v)−1mod p 
In short, a set of polynomials Lf is a set of polynomials having 51 pieces of 1, 50 pieces of −1, and 162 pieces of 0 in its factor f0, f1, f2 . . . , fN−1. The private key f is a polynomial that belongs to the set of polynomials Lf. Also, p is an integer such as 3.
On the other hand, the encryption key that is in public (hereinafter referred to as a public key), h (v) is expressed in a following formula.Public key h(v)=private key f(v)−1×polynomial g(v)(mod q)Polynomial g(v)εa set of polynomials Lg=L(263, 24, 24)
The public key h (v) here is a polynomial. Also, q is, for example, an integer of 27.
In the NTRU encryption, encryption is executed based on the following formula by using this public key h (v). In this encryption, an encryption text e1 (v) is output for an input of a message m1 (v).Encryption text e1(v)=p polynomial φ(v)×public key h(v)+m1(v)(mod q)polynomial φ(v)εa set of polynomials Lφ=L(263, 16, 16)
Here, the polynomial φ(v) is selected at random from a set of polynomials Lφ.
In the meantime, the encryption text e1 (v) is decrypted through following two steps using above private keys f (v) and Fp (v), and a message m1′(v) is acquired.a(v)=private key f(v)×encryption text e1(v)(mod q)  (1)m1′(v)=private key Fp(v)×a(v)(mod p)  (2)
By the way, for breaking the code, there are two types of attacks: passive attacks and active attacks. Encryption such as RSA encryption, EIGamal encryption and NTRU encryption is created based on the assumption against the passive attacks only. The passive attacks, the active attacks, RSA encryption and EIGamal encryption are described in detail in the Literature 1.
Recently, a security proof scheming technology, which converts a general encryption method to a security proof scheme, is suggested as an encryption algorithm improvement technology that enhances a security level against any kind of attacks.
There is a method of using a hash function called as FOSRT in the security proof scheming technique.
FOSRT and the application of FOSRT to the NTRU encryption are described in detail in Jeffrey Hoffstein and Joseph H. Silverman, “Protecting NTRU Against Chosen Ciphertext and Reaction Attacks”, NTRU Cryptosystems Technical Report #016, 2000 (referred to as “Literature 3”). The hash function is described in detail in the Literature 1.
The following is to explain a concrete method of FOSRT.
Encryption with FOSRT is executed through following three steps, and the encryption text E is output for an input of the message M.
(The First Step) A random number R1 is concatenated to the message M, and the concatenated message M∥R1 is acquired.
(The Second Step) A hash function value ha for the message M∥R1 is acquired based on the hash function.Ha=H(M∥R1)(The Third Step) The message M∥R1 and the hash function value ha are encrypted based on the encryption algorithm, and an encryption text E is acquired.E=Enc(M|R1, ha)
Next, the decryption by FOSRT is explained.
(The First Step) The encryption text E is decrypted and a message M∥R1′ is acquired.Dec(E)=M∥R1′(The Second Step) A hash function value ha′ of the message M∥R1′ is acquired based on the hash function.ha′=H(M∥R1′)(The Third Step) Encryption is executed based on the message M∥R1′, the hash function value ha′, and the same algorithm as one used for the above encryption, and an encryption text E′ is acquired.E′=Enc(M∥R1′, ha′)(The Fourth Step) If the encryption text E and the encryption text E′ are inconsistent, there is no output. If consistent, the message M∥R1′ is divided into the message M′ and the random number R1′, and the required message M′ is acquired.
A method for encryption and decryption when this FOSRT is applied to the NTRU encryption is explained as follows.
The encryption is executed through three steps, and the encryption text e (v) is output for the input of the message M (v).
(The First Step) A random vector R (v) is concatenated to the message M (v), and the message m (v) is acquired, wherein m(v)=M(v)∥R(v)
(The Second Step) A hash function value H (m (v)) of the message m (v) is calculated based on the hash function.
(The Third Step) The encryption text e (v) is acquired based on a formula, encryption text e (v)=pH(m(v))×public key h(v)+m(v)(mod q).
On the other hand, the decryption of the encryption text e (v) is executed through following five steps.
(The First Step) Get a polynomial a(v) based on a(v)=private key f(v)×encryption text e(v)(mod q).
(The Second Step) Get a message m′(v) based on m′(v)=private key Fp(v)×a(v)(mod p).
(The Third Step) Calculate a hash function value H (m′(v)) of the message m′ (v), and get an encryption text e′ (v) based on the encryption text e′ (v)=pH (m′ (v))×public key h(v)+m′ (v)(mod q).
(The Fourth Step) Check if the encryption text e′ (v) is consistent with the encryption text e (v).
(The Fifth Step) If the encryption text e′(v) is consistent with the encryption text e(v), divide m′(v)=M′(v)∥R′(v) (M′(v) is a decrypted message, and R′(v) is a random vector), and output the message M′ (v).
As explained above, in the encryption and decryption processes when FOSRT is applied to the NTRU encryption, the hash function values, H (M(v)) and H (m′(v)) are required to belong to a set of polynomials Lφ, for example expressed as L (263, 16, 16).
The set of polynomials, Lφ is associated with a set of vectors having 16 pieces of 1, 16 pieces of −1 and 231 pieces of 0 among its factor f0, f1, f2 . . . , fN−1.
Therefore, in association with the hash function value, it needs to get the n-dimensional array consisting of three values, i.e. 16 pieces of 1, 16 pieces of −1, and 231 pieces of 0.
However, in the encryption and decryption processes when FOSRT is applied to the NTRU encryption, these hash function values, H (m (v) and H (m′ (v)) are integers.
Therefore, in order to apply FOSRT to the NTRU encryption, the n-dimensional array, which has n 1 piece(s) of 1, n2 piece(s) of −1, and other element(s) being −1 based on the hash function values, H (m (v)) and H (m′ (v)) must be obtained. Here, n, n1 and n2 are positive integers.
Here, the following conditions need to be met in the method to obtain the n-dimensional array based on the hash function values, H (m(v)) and H (m′(v)).
(1) Always getting the same output for the same input.
(2) Well-balanced distribution of inputs and outputs
(1) means that a different value is not output for the same input. (2) means that there is no case wherein only a specific output value is frequently output for inputs. When FOSRT is applied to the NTRU encryption, decryption would not be possible if both the sender and recipient are not capable of creating the n-dimensional array for output. If (1) is not satisfied, the encryption method itself would not be realized. Also, if (2) is not satisfied, the balance of output distribution for the hash function input would not be retained since the array is not evenly output based on the output value of the hash function value. Therefore, the security level of the hash function is declined. Hence, the security level of the NTRU encryption when FOSRT is applied is declined.
Here, a self-explanatory method to get the n-dimensional array having 1 piece(s) of 1, n 2 piece(s) of −1, and the number of other elements being 0.
FIG. 1 is a flow chart to show the method to get the n-dimensional array.
This conversion method inputs n1, n2 and an integer X as a hash function value, and outputs the n-dimensional array VJ having n1 piece(s) of 1, n2 piece(s) of −1, and the other (n−n1−n2) piece(s) of 0. Below supposes the i th element (from left) of the array VJ is VJ [i] (“i” is an integer from 1 to n).
Initially, consider when all of the elements of the array VJ are an array of 0 (Step S901).
Next, let a count value c1 of a counter c1′ equal 1 (Step S902).
Next, let VJ [c1]=1 (Step S903).
Next, increment the count value c1 of the counter c1′ (Step 904).
Next, verify that the count value c1 is >n1 (Step S905). If the count value c1 is not >n1 (No in Step S905), execute the process where VJ [c1]=1 again (Step S903).
If the count value c1 is >n1 (Yes in Step S905), set VJ [c1]=−1 (Step S906).
Next, increment the count value c1 (c1←c1+1) (Step S907).
Next, validate if the count value c1 is >n1+n2 (Step S908). If the count value c1 is not >n1+n2 (No in Step S908), execute the process where VJ [c1]=−1 (Step S906) once again.
If the count value c1 is >n1+n2 (Yes in Step S908), output the array VJ and terminate the process.
In this method, the array VJ output, regardless of the input integer X, has the original array having n1 piece(s) of 1, subsequently, n2 piece(s) of −1, and other elements being 0.
On the other hand, a common key encryption method, which encrypts a sending message with a key and decrypts it with the same key, is available as a private communication method. In the common key encryption method, there is a way to create an encryption text through a data replacement operation. For example, it is done as below.
This replacement method uses an array m[1], m[2], . . . , m[n] and a key Ke (a positive integer) as an input, and outputs an encryption text e[1], e[2], . . . , e[n]. The following example supposes to have two dimensional table tabs [j][i] (1≦j≦n!, 1≦i≦n) in advance.
At first, set 1 in the count value c of the counter c′.
Next, substitute m [c] for e [Tab [K][c]]. This process is executed until the count value c of the counter c′ becomes n.
Then, when the count value c of the counter c′ becomes n, the encryption text e is output and the process is terminated.
Although it is possible to consider such a replacement method is applied to the aforementioned method for obtaining the n-dimensional array based on the hash function value, it requires having n*n piece(s) of tables.
However, the aforementioned self-explanatory method to get the n-dimensional array, its output result inclines towards one type and does not satisfy the above condition (2) (Well-balanced distribution of inputs and outputs). In this case, it looses the effect of applying FOSRT and its security level becomes vulnerable against passive attacks. Therefore, there is a problem wherein the security level of the NTRU encryption declines when FOSRT is applied to the NTRU encryption according to this method.
Also, even if the replacement method used as the above mentioned common key encryption is applied to get the n-dimensional array, it uses a memory table requiring a vast amount of memory, which is regarded as a problem.